package com.lihepeng.leecode.tree.langbuladong;

import com.lihepeng.leecode.tree.TreeNode;

/**
 *给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
 *
 * 一般来说，删除节点可分为两个步骤：
 *
 * 首先找到需要删除的节点；
 * 如果找到了，删除它。
 *
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/delete-node-in-a-bst
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution450 {
    /**
     * 删除节点分为三种情况
     * 直接在 末端节点
     * 只有一个非空子节点
     * 存在两个子节点
     * @param root
     * @param key
     * @return
     */
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root ==null) {
            return null;
        }
        if (root.val == key) {
            if (root.left ==null){
                return root.right;
            }
            if (root.right == null) {
                return root.left;
            }
            // 处理 第三种情况
            // 获取右子树 的最小节点
            TreeNode  minNode = getMin(root.right);
            // 删除右子树的最小节点
            root.right = deleteNode(root.right,minNode.val);
            minNode.left = root.left;
            minNode.right = root.right;
            root = minNode;

        }else if (root.val < key){
           root.right =  deleteNode(root.right,key);

        }else {
            root.left = deleteNode(root.left,key);
        }


        return root;
    }

    /**
     * 获得右子树的子节点
     * @param right
     * @return
     */
    private TreeNode getMin(TreeNode right) {
        while (right.left !=null) {
            right = right.left;

        }
        return right;
    }

    /**
     * 模板代码
     * 二叉搜索树 查询某一个值
     */
    void bst(TreeNode root,int target){
        if (root.val == target ) {
            // 找到目标
        }
        if (root.val <target) {
            bst(root.left,target);
        }
        if (root.val > target) {
            bst(root.right,target);
        }

    }
}
